1. Field of the Invention
The present invention relates to state machines, and in particular, to pattern matching applications that represent the patterns to be matched as one or more state machines.
2. Description of the Related Technology
In modern applications it is typical to have patterns that number in the thousands to as many as a million or more. For example, network security applications use large numbers of patterns to detect malicious content such as viruses, spam, and attempts to interfere with proper functioning of the network by gaining unauthorized access to resources and/or hampering performance. Recent advances in technology have made it feasible to do more than packet header inspection by using high-speed hardware that can look at all the bytes in a packet using a programmable state machine engine. Such a packet inspection engine may execute instructions that are, for example, created by a compiler that converts regular expressions into a deterministic finite automata (DFA), which is represented by the instructions.
Because high speed may be important, executable state machine instructions are stored in a manner that is conducive to fast access. This is generally at the expense of consuming more space. For example, 4,000 regular expressions that detect network intrusion can require 200 MB or more of storage when compiled for efficient execution. However, this is in opposition to the requirements of lower cost consumer products which may only have, for example, 50 MB or less available.